package test.day06;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class OrderTravalBTree {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		while(root!=null||!stack.isEmpty()){
			while(root!=null){
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			list.add(root.val);
			root = root.right;
		}
		return list;
	}

	// 递归先序遍历
	public static void recursionPreorderTraversal(TreeNode root) {
		if (root != null) {
			System.out.print(root.val + " ");
			recursionPreorderTraversal(root.left);
			recursionPreorderTraversal(root.right);
		}
	}

	// 非递归先序遍历
	public static void preorderTraversal(TreeNode root) {
		// 用来暂存节点的栈
		Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
		// 新建一个游标节点为根节点
		TreeNode node = root;
		// 当遍历到最后一个节点的时候，无论它的左右子树都为空，并且栈也为空
		// 所以，只要不同时满足这两点，都需要进入循环
		while (node != null || !treeNodeStack.isEmpty()) {
			// 若当前考查节点非空，则输出该节点的值
			// 由考查顺序得知，需要一直往左走
			while (node != null) {
				System.out.print(node.val + " ");
				// 为了之后能找到该节点的右子树，暂存该节点
				treeNodeStack.push(node);
				node = node.left;
			}
			// 一直到左子树为空，则开始考虑右子树
			// 如果栈已空，就不需要再考虑
			// 弹出栈顶元素，将游标等于该节点的右子树
			if (!treeNodeStack.isEmpty()) {
				node = treeNodeStack.pop();
				node = node.right;
			}
		}
	}

	// 递归中序遍历
	public static void recursionMiddleorderTraversal(TreeNode root) {
		if (root != null) {
			recursionMiddleorderTraversal(root.left);
			System.out.print(root.val + " ");
			recursionMiddleorderTraversal(root.right);
		}
	}

	// 非递归中序遍历
	public static void middleorderTraversal(TreeNode root) {
		Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
		TreeNode node = root;
		while (node != null || !treeNodeStack.isEmpty()) {
			while (node != null) {
				treeNodeStack.push(node);
				node = node.left;
			}
			if (!treeNodeStack.isEmpty()) {
				node = treeNodeStack.pop();
				System.out.print(node.val + " ");
				node = node.right;
			}
		}
	}

	// 递归后序遍历
	public static void recursionPostorderTraversal(TreeNode root) {
		if (root != null) {
			recursionPostorderTraversal(root.left);
			recursionPostorderTraversal(root.right);
			System.out.print(root.val + " ");
		}
	}

	// 非递归后序遍历
	public static void postorderTraversal(TreeNode root) {
		Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
		TreeNode node = root;
		TreeNode lastVisit = root;
		while (node != null || !treeNodeStack.isEmpty()) {
			while (node != null) {
				treeNodeStack.push(node);
				node = node.left;
			}
			//查看当前栈顶元素
			node = treeNodeStack.peek();
			//如果其右子树也为空，或者右子树已经访问
			//则可以直接输出当前节点的值
			if (node.right == null || node.right == lastVisit) {
				System.out.print(node.val + " ");
				treeNodeStack.pop();
				lastVisit = node;
				node = null;
			} else {
				//否则，继续遍历右子树
				node = node.right;
			}
		}
	}

	public static void main(String[] args) {
		OrderTravalBTree midOrderTravalBTree = new OrderTravalBTree();
		TreeNode treeNode1 = new TreeNode(1);
		TreeNode treeNode2 = new TreeNode(2);
		TreeNode treeNode3 = new TreeNode(3);
		TreeNode treeNode4 = new TreeNode(4);
		TreeNode treeNode5 = new TreeNode(5);
		TreeNode treeNode6 = new TreeNode(6);
		TreeNode treeNode7 = new TreeNode(7);
		TreeNode treeNode8 = new TreeNode(8);
		treeNode1.left = treeNode2;
		treeNode1.right = treeNode3;
		treeNode2.left = treeNode4;
		treeNode4.right = treeNode6;
		treeNode6.left = treeNode7;
		treeNode6.right = treeNode8;
		treeNode3.right = treeNode5;
		preorderTraversal(treeNode1);
		middleorderTraversal(treeNode1);
		postorderTraversal(treeNode1);

	}
}
